\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{color}
\usepackage{graphicx} % para insertar imagenes
\usepackage{verbatim}

\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}

\title{{\sc\normalsize Sistemas Operativos}\\{\bf Trabajo Práctico Nº2\\ \Pa} {\texttt Grupo 12}}
\author{\begin{tabular}{lcr}
Carla Livorno & 424/08 & carlalivorno@hotmail.com\\Thomas Fischer & 489/08 & tfischer@dc.uba.ar
\end{tabular}}
\date{\VSP \normalsize{Noviembre 2010}}
%\date{}
\begin{document}
\begin{titlepage}
\maketitle
\end{titlepage}
\newpage

\begin{section}{Introducción}

	La idea de este trabajo es implementar un servidor multi cliente para
	reemplazar al existente pero "menos realista" \texttt{servidor\_mono},
	que simula la evacuación de un pabellón.
	
	Este nuevo servidor puede atender a más de un cliente a la vez.
	Para lograr esto, cada vez que un cliente se conecta creamos un thread
	nuevo que se ocupa exclusivamente de atender los pedidos de ese cliente
	en particular. Así, por cada cliente tenemos un thread dedicado.
	
	Si el scheduler usado no sufre de inanición, alterna la ejecución de los
	threads, por lo cuál todos los clientes se ejecutan de manera concurrente.
	Dado que los servidores dedicados de los clientes hacen uso de los mismos
	datos para interactuar entre ellos y el medio, se crean condiciones
	de carrera que hay que tener en cuenta para que el programa conserve
	la correctitud.
	Para esto, usamos las herramientas de sincronización que nos brinda la
	API de linux.

\end{section}

\begin{section}{Implementación}

	Por cada posición del aula, se crea una condición de carrera entre
	los clientes por acceder a cada una de ellas. Por ejemplo,
	consideremos el siguiente código presente en los clientes:

	\begin{verbatim}
		si (PuedoMovermeA(x,y))
		    MovermeA(x,y)
	\end{verbatim}
	
	Varios hilos de ejecución podrían querer moverse al último lugar libre
	de una celda simultáneamente, y cortar su ejecución inmediatamente después,
	o sea, exactamente entre las dos líneas presentadas.
	El resultado va a ser que todos los clientes van a poder moverse a la celda,
	excediendo la capacidad de la misma por un problema de concurrencia.
	
	Luego necesitamos algo que garantice exclusión mutua en cada celda a cada
	cliente. Para esto modificamos la estructura \texttt{t\_aula} existente agregando
	una matriz (del mismo tamaño que \texttt{posiciones}) de mutexes brindados
	por la librería \texttt{pthreads}. Es decir, mantenemos un mutex por cada
	posición en el aula.

	Por otro lado, tenemos que administrar los rescatistas disponibles para que
	coloquen máscaras a los clientes si estan disponibles.
	Sólo pueden socorrer a uno a la vez. Por lo tanto usamos
	un semáforo para restringir el uso de los mismos, inicializado
	en la cantidad de socorristas disponibles. Esto nos garantiza
	que no va a haber más clientes que socorristas siendo atendidos
	simultáneamente.	
\end{section}

\begin{section}{Dificultades encontradas}
	En un primer intento por solucionar las condiciones de carrera entre los clientes pensamos en tener un mutex para toda el aula, es decir, mientras un alumno tenga el acceso a alguna posición del aula ningún otro podrá acceder a ninguna de las posiciones de la misma (en particular a la que es accedida por el primero), asi nos aseguramos que no haya otro cliente que cambie el valor de una variable produciendo inconsistencias. El problema de esa implementación es que si el cliente es desalojado antes de liberar el lock, hasta que no vuelva a tocarle el turno para ejecutar y pueda liberarlo ningún otro cliente va a poder moverse ya que al pedir el lock se va a encontrar con que esta ocupado.
	Esta solución es correcta pero ineficiente porque se pierde el paralelismo, por eso optamos por implementar la solución antes mencionada.\\

	Por otro lado, en la solución implementada puede pasar que un cliente pida el lock de la posición a la que pretende moverse, pueda hacerlo por lo que incremente el contador de esa posición e inmediatamente después de eso sea desalojado. De esa forma, el alumno va a estar en dos posiciónes del aula a la vez, recién cuando vuelva a tocarle el turno de ejecución va a decrementar la posición del aula donde estaba previamente a moverse. Esto es un problema menor, porque si se da esa inconsistencia y un alumno quiere moverse a la posición todavía no actualizada posiblemente no pueda hacerlo pero va a poder moverse la siguiente vez que le toque el turno para ejecutar. Es decir, en el peor de los casos tarda un poco más pero no es un problema de correctitud. Así y todo esta solución es mejor a la otra ya que al bloquear una posición del aula en vez del aula completa, un alumno no impide a otro moverse salvo esa excepción.
\end{section}

\begin{section}{Deadlock}
	Podemos decir que nuestra implementación está libre de deadlock porque no se cumple al menos una de las cuatro condiciones de Coffman (Hold and wait).
	El único recurso compartido por el que compiten los clientes es la memoria, ya que  pretenden consultar y/o modificar variables compartidas. Para eso necesitan obtener el acceso a la sección crítica correspondiente.
	Dado que ningún proceso necesita solicitar más de un lock a la vez, no pasa que algún proceso reserve un lock a pesar de necesitar otro.
\end{section}

\begin{section}{Observaciones}
	Si se ejecuta el \texttt{servidor\_multi} con el \texttt{server\_tester.py} pierde el sentido acotar la cantidad de rescatistas, es más, mientras un alumno esta siendo atendido por un rescatista ningún otro puede moverse. Esto se debe a que el \texttt{receive} es bloqueante, entonces cuando un alumno llega a la puerta el proceso \texttt{server\_tester.py} se bloquea esperando la respuesta en la función \texttt{esperarMascara}. Recién cuando el alumno queda libre, es decir, el cliente recibe la respuesta \texttt{LIBRE!} del servidor, los demás alumnos pueden seguir moviendose hacia la salida o ser atendidos por un rescatista.
\end{section}

\end{document}
